import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class MinCut {

    List<String> list = new ArrayList<>();
    int ans = Integer.MAX_VALUE;
    public int minCut1(String s) {
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(dp[i], true);
        }
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i + 1; j < n; j++) {
                dp[i][j] = s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1];
            }
        }
        process(dp, s, 0);
        return ans - 1;
    }

    public void process(boolean[][] dp, String s, int i) {
        if (i == s.length()) {
            ans = Math.min(ans, list.size());
            return;
        }
        for (int j = i; j < s.length(); j++) {
            if (dp[i][j] && list.size() <= ans - 1) {
                list.add(s.substring(i, j + 1));
                process(dp, s, j + 1);
                list.remove(list.size() - 1);
            }
        }
    }

    public int minCut(String s) {
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(dp[i], true);
        }
        int[] ans = new int[n + 1];
        ans[n] = -1;
        for (int i = n - 1; i >= 0; i--) {
            ans[i] = ans[i + 1] + 1;
            for (int j = i + 1; j < n; j++) {
                dp[i][j] = s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1];
                if (dp[i][j]) ans[i] = Math.min(ans[i], ans[j - 1] + 1);
            }
        }
        return ans[0];
    }
}
